{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "#这个题目需要解决链表的问题\n",
    "我们先来模拟一下链表"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "source": [
    "a = ListNode(10086)\n",
    "b = a\n",
    "for i in range(4):\n",
    "    temp = ListNode(i)  #构造下一个节点\n",
    "    b.next = temp   # 把本节点next 指向 下一个节点\n",
    "    b = b.next      # b变换到下一个节点。\n",
    "\n",
    "b.next = a  # 把最后的节点与a相连，形成环形节点\n",
    "print(a.next.next.val)\n",
    "print(a.next.next.next.next.next.val)"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "1\n",
      "10086\n"
     ]
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "由此可以形成环形链表：\n",
    "10086 -> 0 -> 1 -> 2 -> 3"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "接下来可以看看题目：\n",
    "给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。\n",
    "\n",
    "请你将两个数相加，并以相同形式返回一个表示和的链表。\n",
    "\n",
    "你可以假设除了数字 0 之外，这两个数都不会以 0 开头。\n",
    "\n",
    " \n",
    "\n",
    "示例 1：\n",
    "```\n",
    "输入：l1 = [2,4,3], l2 = [5,6,4]\n",
    "输出：[7,0,8]\n",
    "解释：342 + 465 = 807.\n",
    "```\n",
    "示例 2：\n",
    "```\n",
    "输入：l1 = [0], l2 = [0]\n",
    "输出：[0]\n",
    "```\n",
    "示例 3：\n",
    "```\n",
    "输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]\n",
    "输出：[8,9,9,9,0,0,0,1]\n",
    "```\n",
    "\n",
    "提示：\n",
    "- 每个链表中的节点数在范围 [1, 100] 内\n",
    "- 0 <= Node.val <= 9\n",
    "- 题目数据保证列表表示的数字不含前导零\n"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "source": [
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if l1:\n",
    "            if l2:\n",
    "                dummy = ListNode(0)\n",
    "                p = dummy\n",
    "                carry = 0 #10位\n",
    "\n",
    "                while l1 and l2:\n",
    "                    p.next = ListNode((l1.val + l2.val + carry) % 10)\n",
    "                    carry = (l1.val + l2.val + carry) // 10\n",
    "                    l1 = l1.next\n",
    "                    l2 = l2.next\n",
    "                    p = p.next\n",
    "                if l2:\n",
    "                    while l2:\n",
    "                        p.next = ListNode((l2.val + carry) % 10)\n",
    "                        carry = (l2.val + carry) // 10\n",
    "                        l2 = l2.next\n",
    "                        p = p.next\n",
    "                if l1:\n",
    "                    while l1:\n",
    "                        p.next = ListNode((l1.val + carry) % 10)\n",
    "                        carry = (l1.val + carry) // 10\n",
    "                        l1 = l1.next\n",
    "                        p = p.next\n",
    "                if carry == 1:\n",
    "                    p.next = ListNode(1)\n",
    "                \n",
    "                return dummy.next\n",
    "\n",
    "            return l1\n",
    "        return l2\n",
    "\n",
    "def list_node(l):\n",
    "    dummy = ListNode(0)\n",
    "    p = dummy\n",
    "    for i in l:\n",
    "        temp = ListNode(i)\n",
    "        p.next = temp\n",
    "        p = p.next\n",
    "    return dummy.next\n",
    "\n",
    "def main():\n",
    "    l1 = [9,9,9,9,9,9,9,9]\n",
    "    l2 = [9,9,9,9]\n",
    "    l1_node = list_node(l1)\n",
    "    l2_node = list_node(l2)\n",
    "    \n",
    "    a = Solution()\n",
    "    b = a.addTwoNumbers(l1_node, l2_node)\n",
    "    list = []\n",
    "    while b:\n",
    "        list.append(b.val)\n",
    "        b = b.next\n",
    "        \n",
    "    print(list)\n",
    "    \n",
    "if __name__ == '__main__':\n",
    "    main()  #在外部调试需要把列表进行转换成链表，调用类方式进行leetcode模拟"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[8, 9, 9, 9, 0, 0, 0, 0, 1]\n"
     ]
    }
   ],
   "metadata": {}
  }
 ],
 "metadata": {
  "orig_nbformat": 4,
  "language_info": {
   "name": "python",
   "version": "3.9.0",
   "mimetype": "text/x-python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "pygments_lexer": "ipython3",
   "nbconvert_exporter": "python",
   "file_extension": ".py"
  },
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3.9.0 64-bit ('universe': virtualenv)"
  },
  "interpreter": {
   "hash": "efc9d12c894566d142e82a9dae601d559d62f10cdf97a3f3ead6efac69d368e5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}